struct ShortestPath_Dijkstra{

using weight_t = long long;

struct edge_t{
    int from;
    int to;
    weight_t w;
    edge_t(int a, int b, weight_t c):from(a),to(b),w(c){}
};

int N;
vector<vector<edge_t>> G;

ShortestPath_Dijkstra():Q([](const pair<int, weight_t> & a, const pair<int, weight_t> & b){
    if(a.second != b.second) return a.second > b.second;
    return a.first > b.first;
}){}

void init(int N, int m){
    G.assign((N = N) + 1, {});
}

void mkDiEdge(int a, int b, int c){
    G[a].push_back({a, b, c});  
}

void mkBiEdge(int a, int b, int c){
    mkDiEdge(a, b, c);
    mkDiEdge(b, a, c);
}

void Dijkstra(int s){
    Q.clear();
    D.assign(N + 1, inf());
    Pre.assign(N + 1, 0);
    Flag.assign(N + 1, 0);
    Q.push({s, D[s] = 0});
    while(1){
        while(not Q.empty() and Flag[Q.top().first]) Q.pop();
        if(Q.empty()) break;

        auto h = Q.top(); Q.pop();
        Flag[h.first] = 1;

        int v;
        weight_t tmp;
        for(const auto & e : G[h.first]){
            if(Flag[v = e.to] or D[v] <= (tmp = h.second + e.w)) continue;
            Q.push({v, D[v] = tmp});
            Pre[v] = h.first;
        }
    }
    return;
}

static weight_t inf() {
    static const weight_t INF = 0x7F8F9FAFBFCFDFEF;
    return INF;
}

__gnu_pbds::priority_queue<
    pair<int, weight_t>, 
    function<bool(const pair<int, weight_t> &, const pair<int, weight_t> &)>
> Q;

vector<weight_t> D; // D[i]表示s到i的最短距离
vector<int> Pre; // 从s到i的最短路径会经过pre[i]
vector<int> Flag; // 标记数组

};